The present invention relates generally to error control coding, and more specifically, to a configurable error control coding (ECC) engine that has a specialized instruction set tailored for ECC tasks.
In digital electronic systems, information is represented in a binary format (i.e., as a series of 0""s and 1""s). When information in a binary format is transported from a first point to a second point or stored on a magnetic media, there is the possibility of an error occurring during the transmission and reception process. For example, a xe2x80x9c1xe2x80x9d can be interpreted as a xe2x80x9c0xe2x80x9d, or a xe2x80x9c0xe2x80x9d can be interpreted as a xe2x80x9c1xe2x80x9d. There may be any number of reasons for the error. For example, media defects, electronic noise, component failures, poor connections, deterioration of data due to age, multi-path fading, other factors, or a combination thereof, can cause these errors. When a bit of information is mistakenly interpreted, a bit error has occurred.
To address the problem of bit errors, error correction schemes have been developed. Error correction is simply the use of techniques to detect bit errors and to correct them. Information can be conveyed as a group of bits. Typically, error correction schemes add xe2x80x9credundantxe2x80x9d bits (i.e., extra bits) to the information. The extra bits add a particular structure to the information. Consequently, if the structure is altered by errors, the changes can be detected and corrected.
Some have used the following analogy to the English language to describe error correction schemes. The English language is based on the English alphabet and words that are formed by utilizing the letters in that alphabet. It is obvious that not all possible combinations of the English alphabet form xe2x80x9cmeaningful wordsxe2x80x9d where xe2x80x9cmeaningful wordsxe2x80x9d are defined as those words listed in a dictionary of the English language. Errors that occur when transmitting or storing English words can be detected by determining if the received word is defined by the dictionary. If the received word does not correspond with any word in the dictionary, errors in the word may be corrected by finding a meaningful word that is closest to the received word. Conceptually, error correction systems perform in a similar fashion to this analogy described above.
We live in a communication intensive society where the accurate transfer of information is important. Data communication via a wired system using cables or telephone lines is generally more reliable in the sense that there are fewer transmission errors than in a wireless communication system. One common example of wireless communications is the use of cellular telephones for voice communication, and increasingly, for data transfer.
In general, when designing a wireless system, the transmission errors in the communication channel need to be addressed. One situation that creates transmission errors in a wireless system is the existence of noise that can be man-made (e.g., radio frequency (RF) sources, electromagnetic field generated by electric sources, etc.), that can result from natural phenomenon (e.g., lightening, atmospheric conditions, etc.) or that can stem from the intrinsic thermal noise of the receiver. The noise can corrupt data that is being transferred. For example, in the cell phone example, the noise can manifest itself as static or as a loss of the voice data. The loss of voice data can be the loss of a spoken word, phrase, or entire sentence. If the noise is severe, the connection between the cellular telephone and the base station can be terminated. Accordingly, one goal of wireless system design is to provide a mechanism for addressing the transmission errors in the channel.
A second problem associated with a wireless system is that the communication channel is lossy (i.e., a signal may be at a high amplitude at the transmitting antenna, but of low amplitude a few miles away). Since the rate of transmission errors (i.e., the error rate) decreases with a higher signal-to-noise ratio, the error rate can be decreased by increasing the power transmitted by the cellular telephone, for example. Unfortunately, using higher power for transmission decreases the battery life of the cellular telephone that inconveniences users of such phones. Accordingly, it is desirable for a mechanism to correct transmission errors.
In this regard, in order too address the lossy and noisy traits of a wireless communication channel, designers commonly employ error correction systems. Error correction systems add additional bits to the data transmission, which are referred to as error correction bits, to detect and correct bit errors. There are many different types of error correction algorithms that can be effectively employed to detect and correct for bit errors in wireless systems, thereby increasing the accuracy of data communications and decreasing the number of errors encountered.
One approach to implementing the error correction algorithms is to utilize processors with a general arithmetic logic unit (ALU) or general floating point unit (FPU). Unfortunately, this approach does not provide (1) adequate performance and (2) the appropriate level of abstraction for error correction and detection tasks.
First, these general ALUs or FPUs provide only tolerable performance for error control coding (ECC) since the general processor must be able to perform many different tasks, only one of which is error correction related tasks. Consequently, the general ALU or FPU is not optimized for ECC tasks.
Second, a programmer who is writing code to implement a particular error detection and correction algorithm is required to program at an inappropriate level of abstraction. For example, the programmer is forced to write many lines of code in a development language, such as xe2x80x9cCxe2x80x9d programming language, just to implement a single error detection or error correction task. in a typical error detection and correction system, there is an encoder block and a decoder block with several functional blocks within each. The encoder block, for example, may include a convolutional encoder and interleaver that each would require one or more pages of program code in xe2x80x9cCxe2x80x9d to implement. Similarly, the decoder block, which may include a convolutional decoder and a de-interleaver, each would require one or more pages of code to implement. When the number of lines of required code increases, the development costs of a project generally increases proportionally. Furthermore, more lines of code leads to longer time to debug and to verify the proper operation of the code.
Consequently, it would be desirable for there to be an engine that can easily and simply implement a particular error correction task (e.g., convolutional encoder) without many lines of code. By simplifying and reducing the number of instructions that a developer has to write to implement an error detection or correction task, the attendant complexities and difficulties in developing code at an unnecessarily low level of abstraction can be decreased.
Programming at an unnecessarily low level of abstraction also adversely affects performance. For example, a single error control coding algorithm often involves many lines of instructions in a loop, where each execution of the loop requires multiple clock cycles to generate a single bit of output. In this regard, it is desirable for a mechanism for allowing a designer to specify an algorithm with a single instruction and for reducing the number of clock cycles needed to generate the output bits of error control coding algorithms.
Another approach to implementing the error correction and detection algorithms is to utilize specialized application specific integrated circuits (ASICs) that are hard-wired to perform a particular error-coding algorithm. This approach offers very fast execution and improves the performance when compared with the first approach. Unfortunately, new wireless communication protocols that specify different error correction algorithms are always being developed. In addition, current protocols are subject to numerous revisions and changes that also affect the type of error detection and correction algorithms used.
In this regard, the ASICs are inflexible in that when a new error coding algorithm is needed or a new standard (e.g., a wireless standard) is required, an entirely new ASIC that is hard-wired for the new algorithm or standard needs to be developed. As can be appreciated, the inflexibility of this approach and inability to adapt to new standards undesirably increases product development costs and time. Consequently, a mechanism is needed to allow a computation unit to be flexible enough to adapt to these new algorithms without the costs and development time required by the second prior art approach.
Based on the foregoing, it is clearly desirable to provide an apparatus and method for efficiently performing error detection and correction tasks, that provides an appropriate level abstraction for error correction methods, and that is flexible to adapt to changes in error coding algorithms.
An apparatus and method for efficiently performing error control coding (ECC), such as error detection and correction (EDAC) tasks, are provided. An important aspect of the present invention is the provision of an error control coding (ECC) engine that responds to a specialized ECC instruction set having a plurality of instructions. Examples of these instructions include a convolutional encoding instruction, a convolutional decoding instruction, an interleave instruction, a bit manipulation instruction, and a cyclic redundancy code (CRC) instruction. The ECC engine has a plurality of functional building blocks (e.g., a configurable convolutional encoding functional block, a configurable convolutional decoding functional block, and a configurable cyclic redundancy code (CRC) check functional block) that can be programmed or configured. A single instruction provided to the error control coding engine configures one of the functional blocks to execute an error control coding algorithm specified by the instruction. Each instruction also includes a plurality of fields that can be set by the user to specify parameters of the ECC algorithm. Each modified instruction dynamically re-configures one of the functional building blocks to implement a different ECC algorithm specified in by the instruction.
Preferably, each ECC task can be described as a single command or instruction for the ease of programming. Instead of having to program many lines of code to implement an ECC task, by using the programmable ECC engine of the present invention, the programmer can specify a desired ECC task with a single instruction. The instruction set of the ECC engine of the present invention is tailored at the optimal level of programming abstraction for ECC task, thereby greatly simplifying the design, programming, and implementation of these ECC tasks.
In the presently preferred embodiment, the configurable ECC engine of the present invention is incorporated with a processor. The processor includes an arithmetic logic unit (ALU) for executing non-error detection and correction tasks and the ECC engine of the present invention for executing ECC tasks in response to special ECC instructions. The special instruction set is incorporated into the general instruction set utilized by the processor. An instruction decoder that is coupled to the general purpose ALU and the ECC engine is provided. The instruction decoder decodes and routes instructions to an appropriate processing unit (e.g., the instruction decoder can route non-ECC instructions to the general purpose ALU for execution and route ECC instructions to the ECC engine for execution.
In an alternative embodiment, the system includes a processor having a general purpose ALU for executing non-ECC tasks and a co-processor having the configurable ECC engine of the present invention for executing ECC tasks. In this embodiment, a shared memory is provided. The processor and the co-processor can utilize the shared memory to communicate information (e.g., a specialized error correction code instruction) therebetween. An advantage of this embodiment is that after passing control to the co-processor of an ECC task, the processor is free to execute other non-ECC tasks while waiting for the co-processor to return results.